package day04;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2023/2/4 23:27
 */

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给你一个下标从 0 开始的 m x n 二进制 矩阵 grid 。你可以从一个格子 (row, col) 移动到格子 (row + 1, col) 或者 (row, col + 1) ，前提是前往的格子值为 1 。如果从 (0, 0) 到 (m - 1, n - 1) 没有任何路径，我们称该矩阵是 不连通 的。
 *
 * 你可以翻转 最多一个 格子的值（也可以不翻转）。你 不能翻转 格子 (0, 0) 和 (m - 1, n - 1) 。
 *
 * 如果可以使矩阵不连通，请你返回 true ，否则返回 false 。
 *
 * 注意 ，翻转一个格子的值，可以使它的值从 0 变 1 ，或从 1 变 0 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：grid = [[1,1,1],[1,0,0],[1,1,1]]
 * 输出：true
 * 解释：按照上图所示我们翻转蓝色格子里的值，翻转后从 (0, 0) 到 (2, 2) 没有路径。
 * 示例 2：
 *
 *
 *
 * 输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
 * 输出：false
 * 解释：无法翻转至多一个格子，使 (0, 0) 到 (2, 2) 没有路径。
 */
public class Solution12 {
    public boolean isPossibleToCutPath(int[][] grid) {
        int m = grid.length,n = grid[0].length;
        if(m==1||n==1){
            return true;
        }
        Queue<int[]> bfs = new LinkedList<>();
        if(grid[0][1]!=0){
            bfs.add(new int[]{0,1});
        }
        if(grid[1][0]!=0){
            bfs.add(new int[]{1,0});
        }
        while (bfs.size()>1){
            int size = bfs.size();
            for (int i = 0; i < size; i++) {
                int[] poll = bfs.poll();
                int mL = poll[0]+1;
                int nL = poll[1]+1;
                if(mL<m&&grid[mL][poll[1]]!=0){
                    if(mL == m-1&&poll[1]==n-1){
                        return false;
                    }else {
                        grid[mL][poll[1]]=0;
                        bfs.add(new int[]{mL,poll[1]});
                    }
                }
                if(nL<n&&grid[poll[0]][nL]!=0){
                    if(poll[0] == m-1&&nL==n-1){
                        return false;
                    }else {
                        grid[poll[0]][nL]=0;
                        bfs.add(new int[]{poll[0],nL});
                    }
                }
            }
        }
        return true;
    }
}
